package hot100;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class topKFrequent2 {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        // 统计频率
        for (int x : nums) {
            hash.put(x, hash.getOrDefault(x, 0) + 1);
        }
        // 按频率升序（小根堆）
        PriorityQueue<Integer> que = new PriorityQueue<>(
                (a, b) -> hash.get(a) - hash.get(b));
        // 维护堆大小为k
        for (int key : hash.keySet()) {
            que.offer(key);
            if (que.size() > k) {
                que.poll();
            }
        }
        // 逆序输出结果
        int[] ret = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            ret[i] = que.poll();
        }
        return ret;
    }
}
